home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / ast_comp / rdp.doc < prev    next >
Text File  |  1994-02-20  |  15KB  |  310 lines
  1. ** RDP release version 1.00 flyer. Adrian Johnstone 16 February 1994 **
  2.  
  3. RDP - a recursive descent parser generator
  4.  
  5. RDP compiles attributed LL(1) grammars decorated with C-language semantic
  6. actions into recursive descent compilers. RDP is written in strict ANSI C
  7. and produces strict ANSI C. RDP was developed using Borland C 3.1 on a PC
  8. and has also been built with no problems on Alpha/OSF-1, DECstation/Ultrix
  9. and Sun 4/SunOS hosts. The definition of strict ANSI here means compiling
  10. with gcc -Wall -pedantic -ANSI and getting no warning messages.
  11.  
  12. RDP itself and the language processors it generates use standard symbol,
  13. set and scanner modules. The RDP scanner is programmed by loading tokens
  14. into the symbol table at the start of each run.
  15.  
  16. RDP produces complete runnable programs with built-in help information and
  17. command line switches that are specified as part of the EBNF file. In this
  18. sense RDP output is far more shrink-wrapped than the usual parser generators
  19. which helps beginning students. RDP can generate itself which is a nice
  20. demonstration of the bootstrapping technique used for porting compilers to
  21. new architectures.
  22.  
  23. I wrote RDP because in October I start giving a course on compiler design.
  24. I don't think the world needs another course on parsing techniques and am
  25. really interested in code generation for exotic processors, so I tried to
  26. produce a compact parser generator that would enable undergraduates to rip
  27. through the syntax and standard code generation parts of the syllabus in a
  28. few weeks, thus leaving me time to get into the black arts of code
  29. scheduling and optimisation.
  30.  
  31. What you get.
  32.  
  33. - An implementation of Pascal style set-handling in C.
  34.  
  35. - A hash-coded symbol table with support for scoping and arbitrary user data
  36.  
  37. - A programmable high-speed scanner with integrated error handling and
  38.   hooks for macros (RDP is being used to generate assemblers for two novel
  39.   microprocessors in addition to the usual applications of LL(1) parsers).
  40.  
  41. - The source to a hand-coded version of the RDP translator. RDP checks that
  42.   the source grammar is LL(1) and explains exactly why a non-LL(1) grammar
  43.   is unacceptable. RDP does not attempt to rework a grammar by itself.
  44.  
  45. - A decorated EBNF file describing RDP that may be processed by the
  46.   hand-coded RDP translator to produce a machine generated version of RDP.
  47.   This is good for boggling undergraduate's minds with.
  48.  
  49. - A decorated EBNF file describing an interpreter for a language called TOY.
  50.  
  51. - An EBNF file describing Pascal which can be used to generate a parser for
  52.   the Pascal language. This description needs some work: it is overstrict
  53.   with respect to semicolons and does not presently handle quites within
  54.   strings.
  55.  
  56. - A pre-built RDP executable for MS-DOS.
  57.  
  58. - Sources, makefiles and Borland 3.1 project files for everything which
  59.   you may use freely on condition that you send copies of any modifications,
  60.   enhancements and ill-conceived changes you might make back to me so that
  61.   I can improve RDP.
  62.  
  63. What you don't get.
  64.  
  65. - Decent manuals (coming Real Soon Now). When the manuals arrive they will
  66.   be called rdp.ps which is a user manual for RDP proper, and rdp_supp.ps
  67.   which is a user manual for the set, symbol and scanner modules. If you
  68.   get a late version of this distribution you might be lucky and find them
  69.   in the kit.
  70.  
  71. - Tutorial information on parsing and compiling (try Wirth's Algorithms +
  72.   Data Structures = Programs, Chapter 5 or your favourite compiler book).
  73.  
  74. - Warranties. (This code has only just escaped from my personal toolkit.
  75.   I've put a lot of effort into making it fit for others to use, but in
  76.   the very nature of compiler compilers it is hard to test all the angles,
  77.   and the Garbage In - Garbage Out principle holds to the highest degree:
  78.   if you write ill-formed semantic actions you won't find out until you try
  79.   and compile the parser that RDP wrote for you.)
  80.  
  81. What I'd like.
  82.  
  83. - Guinea pigs: I'm sure there are some bad surprises waiting for me, and I'd
  84.   like to find them before October so that my course doesn't get torpedoed.
  85.  
  86. - A C grammar. The supplied Pascal grammar was produced by retrieving the
  87.   yacc Pascal description floating around on the net and hacking it into RDP
  88.   source form (which shortens it a great deal BTW). An obvious first
  89.   project is to do the same for the C grammar and maybe produce a
  90.   pretty-printer based on it.
  91.  
  92. RDP source language.
  93.  
  94. - The RDP source language is a very conventional EBNF supplemented with:
  95.  
  96.     a few pre-defined tokens such as ID (an alphanumeric identifier),
  97.     NEW_ID (an alphanumeric identifier that has not yet been added to
  98.     the symbol table), EOF and EOLN,
  99.  
  100.     some programmable tokens such as STRING and STRING_ESC which define
  101.     Pascal and C style strings respectively,
  102.  
  103.     a set of directives which are mainly used to programme the scanner
  104.     and the help subsystems
  105.  
  106.     a weird construct < sequence > 'token' which is shorthand for
  107.     sequence {'token' sequence}
  108.  
  109.     attributes of the form :identifier which may be attached to production
  110.     names or tokens where they define the type of variable returned on the
  111.     LHS and the name of the receiving variable on the RHS of an ::=
  112.  
  113.     arbitrary C code semantic actions embedded in double quotes. These are
  114.     simply copied into the generated parser.
  115.  
  116. - Here's the RDP grammar written in terms of itself. Tokens are enclosed
  117.   in single quotes, directives and built-in tokens are written in upper case
  118.   and comments are denoted by (* ... *). RDP is case sensitive.
  119.  
  120. (* RDP source grammar *)
  121. unit     ::= { prod | dir} EOF.       (* Zero or more productions or directives *)
  122.  
  123. prod     ::= (ID|NEW_ID) [':'(ID|NEW_ID) {'*'} ] '::=' alt '.' .
  124.  
  125. alt      ::= < seq > '|' .            (* Alternates are separated by | *)
  126.  
  127. seq      ::= { (item_ret [':' (ID | NEW_ID) ] | item_inl) }.
  128.  
  129. item_ret ::= ID | NEW_ID |            (* Production *)
  130.          token |                  (* Token *)
  131. (* Following four are parameterisble tokens for handling strings and comments *)
  132.           'STRING' '(' token ')' |            (* Pascal style string *)
  133.           'STRING_ESC' '(' token token')' |   (* C-style string *)
  134.           'COMMENT' '(' token token ')' |     (* Non-nested comment *)
  135.           'COMMENT_NEST' '(' token token ')'. (* Nestable comment *)
  136.  
  137. item_inl ::= code |                   (* semantic action *)
  138.          '(' alt ')' |            (* do first *)
  139.          '{' alt '}' |            (* zero or more *)
  140.          '[' alt ']' |            (* zero or one *)
  141.          '<' alt '>' token .      (* list: <X>'t' expands to X {'t' X} *)
  142.  
  143. code     ::= STRING_ESC('"' '\\').    (* Inline code is delimited by ".." *)
  144. token    ::= STRING_ESC('\'' '\\').   (* Tokens are delimited by '..' *)
  145. comment  ::= COMMENT_NEST('(*' '*)'). (* Nestable comments are delimited by (*..*) *)
  146.  
  147. dir ::= 'INCLUDE' '(' code ')' |        (* Does for RDP what #include does for C *)
  148.     'HELP' '(' code code  ')' |     (* Add help line and command line switch *)
  149.     'USES' '(' code ')' |           (* Adds a #include to the generated parser *)
  150.     'TITLE' '(' code ')' |          (* Descriptive programme title for help *)
  151.     'SUFFIX' '(' code ')' |         (* Defalt file suffix for scanner input *)
  152.     'PRE_PROCESS' '(' code ')' |    (* Function to call before activating parser *)
  153.     'POST_PROCESS' '(' code ')' |   (* Function to call after activating parser *)
  154.     'OUTPUT_FILE' '(' code ')' |    (* Default output file name *)
  155.     'SET_SIZE' '(' NUMBER ')' |     (* Set maximum set size (must be >= # of tokens *)
  156.     'HASH_SIZE' '(' NUMBER ')' |    (* Number of hash buckets in hash table *)
  157.     'HASH_PRIME' '(' NUMBER ')' |   (* Hash key: see dragon book on hash functions *)
  158.     'TAB_WIDTH' '(' NUMBER ')' |    (* Tab expansion width in listings *)
  159.     'TEXT_SIZE' '(' NUMBER ')' |    (* Default size of text buffer *)
  160.     'MAX_ERRORS' '(' NUMBER ')' |   (* Stop after this many errors *)
  161.     'MAX_WARNINGS' '(' NUMBER ')' | (* Stop after this many warnings *)
  162.     'CASE_INSENSITIVE' |            (* Make scanner case insensitive (cf Pascal) *)
  163.     'SHOW_SKIPS' |                  (* Issue 'Skipping...' informational messges *)
  164.     'NEWLINE_VISIBLE' |             (* Make newlines visisbles (cf Ada comments, assemblers) *)
  165.     'COMMENTS_VISIBLE'.             (* Return comments to parser (cf assemblers) *)
  166.  
  167. (* End of grammar *)
  168.  
  169. How to get RDP.
  170.  
  171. - Use anonymous ftp to cscx.dcs.rhbnc.ac.uk (134.219.200.45) and download
  172.   pub/rdp/rdp.tar.Z if you are a Unix user or pub/rdp/rdp.zip if you are an
  173.   MS-DOS user. Actually both files contain exactly the same distribution kit,
  174.   so you will find an MS-DOS executable in the tar file.
  175.  
  176. - If you only have email access to the Internet, try one of the email based
  177.   ftp servers such as @decwrl.
  178.  
  179. - If you can't manage ftp then I am prepared to send out 3.5in 1.4M disks
  180.   for MS-DOS. If you're really desperate I can supply just any other medium
  181.   that PC's, Amigas, Atari-ST's, Mac's or DEC computers have ever used, but
  182.   I'm very short of time so strange requests may take a while to service.
  183.  
  184. Other machines.
  185.  
  186. - An ex-student of mine is going to try and build RDP for an Amiga. IMHO
  187.   anybody with an ANSI C compiler should have almost no problems building
  188.   from the standard kit. On the other hand K&R compiler users may suffer.
  189.  
  190. Installation.
  191.  
  192. 1 Unpack the distribution kit into a single directory. You should have the
  193.   following files:
  194.  
  195.   buildlog.dos  A log of Borland make and Borland C 3.1 building for DOS
  196.   buildlog.unx  A log of OSF/1 make and GNU CC for Alpha building for Unix
  197.   crash.c       Fatal error handling and memory allocation
  198.   crash.h
  199.   makefile      Customisable make file for Unix and MS-DOS Borland C 3.1
  200.   pascal.bnf    Pascal grammar for building a Pascal parser
  201.   rdp.bnf       Decorated RDP grammar for building machine generated RDP
  202.   rdp.c         Hand written RDP front end
  203.   rdp.h
  204.   rdp.doc       This file
  205.   rdp_aux.c     Auxilliary file containing RDP semantic actions
  206.   rdp_aux.h
  207.   scan.c        A programmable scanner
  208.   scan.h
  209.   set.c         An implmentation of Pascal style sets
  210.   set.h
  211.   symbol.c      A hash code symbol table
  212.   symbol.h
  213.   test.pas      A piece of Pascal for testing the Pascal parser
  214.   test.toy      A piece of Toy for testing the Toy parser
  215.   toy.bnf       Decorated Toy grammar for building Toy interpreter
  216.  
  217. 2 The makefile can be used on Unix or on a PC, but you should edit it to
  218.   make sure that it is configured for your operating system. Select one of
  219.   the two blocks of macro definitons at the top of the file.
  220.  
  221. 3 To build everything, just type 'make'. The default target in the makefile
  222.   builds rdp, the Toy interpreter and the Pascal parser. The Toy interpreter
  223.   is run on test.toy, and the Pascal interpreter is run on test.pas. Neither
  224.   should generate any errors. On successful completion, make uses rdp to
  225.   build rdp_gen, a machine generated version of rdp and then uses rdp_gen to
  226.   reproduce itself. The two machine generated versions are compared with each
  227.   other to make sure that the bootstrap has been successful. They should
  228.   differ only in the program names.
  229.  
  230.   The following messages appearing during the build are normal:
  231.  
  232.   During compilation of toy.c
  233.    Warning toy.c 732: 'base' is assigned a value that is never used in function main
  234.    Warning toy.c 732: 'force' is assigned a value that is never used in function main
  235.  
  236.   During the run of toy on test.toy
  237.    Toy V1.00 Feb 18 1994 20:07:04
  238.    test.toy: toy interpreter OK
  239.     Text mode: 0 errors, 0 warnings
  240.  
  241.   During generation of pascal.c the dangling else causes
  242.    Error: ** Production 'statement__9' contains null but first /\ follow is not empty
  243.  
  244.   During compilation of pascal.c
  245.    Warning pascal.c 1820: 'base' is assigned a value that is never used in function main
  246.    Warning pascal.c 1820: 'force' is assigned a value that is never used in function main
  247.  
  248.   During the run of pascal on test.pas
  249.    Pascal parser V1.00 (generated) Feb 18 1994 20:07:10
  250.     test.pas: 0 errors, 0 warnings
  251.  
  252.  
  253.   During the comparison of the machine generated rdp versions
  254.  
  255.    #include "rdp_genA.h"
  256.    #include "rdp_genB.h"
  257.  
  258.    "Usage: rdp_genA [options] sourcefile \n\n"
  259.    "Usage: rdp_genB [options] sourcefile \n\n"
  260.  
  261.   The buildlog.* files show a complete log for Unix and MS-DOS: if your
  262.   results are different then please let me know.
  263.  
  264. 4 If you type 'make clean' all the object files and the machine generated
  265.   rdp versions will be deleted, leaving the distribution files plus the new
  266.   executables.
  267.  
  268. 5 If you type 'make veryclean' then the directory is cleaned and the
  269.   executables are also deleted.
  270.  
  271. Missing bits to be fixed in version 1.1
  272.  
  273. There are a couple of things that I managed to break whilst preparing this
  274. version. I've run out of time to work on RDP so I'll just note them here and
  275. put out a maintenance release soon, maybe at the end of February 1994.
  276.  
  277. - Presently the RDP text mode scanner is line oriented, so I have removed the
  278.   interpretation of while loops from Toy because they break if the while 
  279.   statement is the first thing on the line. This is top priority to be fixed:
  280.   look out for version 1.1
  281.  
  282. - Late on, I introduced a stupid bug into the handling of comment and string
  283.   delimiters so thatthey must be two characters long to work. Hence /* .. */
  284.   is fine but { } is not. Hence the Pascal parser does not parse comments. This
  285.   will also be fixed in version 1.1.
  286.  
  287. - Due to a subtlety of the order in which sequences are evaluated, rdp_gen
  288.   and its first child differ, so I need to generate rdp_gen's child and
  289.   grandchild to do the convergence check in the makefile. 
  290.  
  291. Enhancements for version 2
  292.  
  293. - RDP parsers have large numbers of constant first and follow sets embedded
  294.   in them. For some applications, especially assemblers, many of these sets
  295.   are identical. In version 2 identical sets will be collapsed. This is only
  296.   likely to save a few kilobytes in even the most pathological parser, but it
  297.   offends my sense of neatness.
  298.  
  299. - Macro handling code will be incorporated directly into the scanner. At the
  300.   moment I do macros within my assemblers (which I'm not releasing for
  301.   public consumption just yet).
  302.  
  303. Comments, queries and requests for code to
  304.  
  305. Dr Adrian Johnstone, CS Dept, Royal Holloway, University of London
  306. Email: adrian@dcs.rhbnc.ac.uk
  307.  
  308.  
  309.  
  310.